$\lceil$ $\rfloor$ FLAME: Differentially Private Federated Learning in the Shuffle Model

摘要

联邦学习(Federation Learning，FL )是一种很有前途的机器学习范式，它可以使分析器在不收集用户原始数据的情况下训练模型。为了保证用户隐私，差分隐私联邦学习得到了广泛的研究。现有的工作主要基于差分隐私的中心模型（curator model） 或本地模型（local model）。然而，两者都有利有弊。curator model允许更高的准确性，但需要可信的分析器。在local model中，用户将本地数据随机化后发送给分析器，虽然不需要可信分析器，但准确率有限。在这项工作中，通过利用最近提出的差分隐私混洗模型中的隐私放大（privacy amplification）效应，我们实现了两个模型的最佳方式，即平衡了curator model中的准确性和不依赖任何可信方的强隐私性。我们首先提出了shuffle模型中的联邦学习框架和在已有工作基础上扩展的一种简单协议（SS-Simple）。我们发现SS-Simple仅在联邦学习中提供了不充分的隐私放大效应，因为模型参数的维度相当大。为了解决这一问题，我们提出了一种增强型协议（SS-Double），通过欠采样来强化隐私放大效应。进一步，当模型规模大于用户数量时，为了提高效用，我们提出了一种采用梯度稀疏技术的改进协议（SS-Topk）。我们还对所提协议的隐私放大效应进行了理论分析和量化评估。在real-world数据集上的实验验证了SS-Topk比基于本地模型的联邦学习提高了60.7 %的测试准确率。值得注意的是，SS-TopkSS-Topk $( 4.696,10 ^{- 5}) - DP$ 下仅损失了1.48 %的准确率。

Introduction

联邦学习（Federation Learning，FL ）是一种很有前途的机器学习范式，它可以使分析器在不收集用户原始数据而只进行本地更新的情况下训练一个中心模型。然而，已有研究表明，共享原始的本地更新可能会损害用户的隐私。为此，差分隐私联邦学习（differentially private federated learning）被广泛研究以提供形式隐私。现有的工作主要基于差分隐私的curator modellocal model $\epsilon$ $n$ $O ( 1 / \epsilon )$ $\Omega(\sqrt{n})$ 为界的。

最近提出的安全混洗模型( secure shuffle model, SS )可以同时实现两种模型的最佳方式，即curator model的准确性和local model的强隐私性。shuffle模型在用户和分析器之间引入了一个混洗器( 如Figure 1(b)所示 )，在将用户的本地随机数据发送到分析器之前对其进行置换。混洗模型的精度增益由隐私放大效应（privacy amplification effect） 得到，这表明在差分隐私的中心视图中，经过混洗的本地随机发生器的（即,匿名化）输出比没有混洗的输出提供了更强的（增强的）隐私。相应地，在混洗模型中需要更少的本地噪声来保护与不可信分析器相同级别的隐私。

然而，在联邦学习中如何使用shuffle模型尚不清楚。尽管少数工作已经研究了诸如比特/实数求和以及直方图等基本任务，但是现有的协议可能并不适用于多维状态的聚合联邦学习。

更新向量的维度以维度因子加剧了本地噪声引起的误差。此外，由于参与一次迭代的用户数量通常为好几千，因此聚合操作会升级为高维任务。我们通过做出以下贡献来解决上述挑战：

我们首次在shuffle模型中提出了一个联邦学习框架FLAME，使得用户享有较强的隐私性，分析器享有模型的准确性。我们首先在FLAME中通过明确信任边界（trust boundary）和细粒化信任分离（trust separation）来形式化我们的隐私目标（表1），然后我们通过扩展一维任务提出了SS - Simple协议。
我们发现，尽管SS - Simple可以实现隐私放大，但是增强的幅度随着本地更新的维度增大而减小（定理2）。
为了减轻这一挑战，我们提出了SS - Double协议，通过子采样来强化隐私放大。正如我们注意到的，通过子采样的增强可能与混洗不兼容，于是我们提出了一种新的虚拟填充（dummy padding）方法并用形式化证明（定理3和定理4）来桥接这两种增强效应。我们证明了SS - Double协议比SS - Simple协议具有数十倍的隐私放大效果（图3）。
SS - DoubleSS - Topk $- k$ 的元素的索引可能会揭示相对于混洗者敏感的信息，因为选择是数据依赖的。我们通过将索引隐私（index privacy）形式化来量化这种隐私威胁，并设计了一种在索引隐私和效用之间灵活权衡的方法。我们注意到索引隐私不会损害对分析器的隐私保护。
最后，我们在真实数据集上进行实验，验证所提出的协议的有效性。结果表明，本文提出的SS - Double中的双重增强3效应和SS - Topk中的私有维度选择显著提高了学习准确率。在不依赖任何可信方的情况下，SS - TopkSS - Topk $( 4.696、10^{- 5}) - DP$ 下仅损失1.48 %的准确率。

预备知识

Curator Model和Local model

$X \simeq_r X'$ 。我们有如下定义：

差分隐私机制的定义： $\mathcal{M}:\mathbb{X}^n\rightarrow \Z$ $(\epsilon, δ)-$ $X \simeq_r X' \in \mathbb{X}^n$ $S\subseteq \Z$ $\text{Pr}[\mathcal{M}(X)\in S]\leq e^\epsilon\text{Pr}[\mathcal{M}(X')\in S]+\delta$

$\mathcal{R}$ $(\epsilon , δ)-LDP$ $( y_1 , \dots, y_n)$ $(\epsilon , δ) - DP$

本地差分隐私的定义： $\mathcal{R}:\mathbb{X}\rightarrow \mathbb{Y}$ $(\epsilon, δ)-$ $x,x'\in\mathbb{X}$ $y\in\mathbb{Y}$ $\text{Pr}[\mathcal{R}(x)=y]\leq e^\epsilon\text{Pr}[\mathcal{R}(x')=y]+\delta$ 。

混洗模型（The Shuffle Model）

$\mathcal{P} = \mathcal{A}\circ\mathcal{S}\circ\mathcal{R}^n$ ，如图1 ( b )所示。

$x∈\mathbb{X}$ $n$ $X = ( x_1 , · · · , x_n)∈\mathbb{X}^n$ $\mathcal{R}:\mathbb{X}→\mathbb{Y}^m$ $\epsilon_l -$ $m$ $m = 1$ $\pi$ $\mathcal{S}:\mathbb{Y}^*→\mathbb{Y}^*$ $\mathcal{A}:\mathbb{Y}^*→\mathbb{Z}$ 将混洗后的消息作为输入，输出解析结果。

$\mathcal{M} = \mathcal{S}\circ \mathcal{R}^n$ $( \epsilon_c , \delta_c) -$ $\mathcal{A}$ $\mathcal{P}$ $\mathcal{M}$ $\mathcal{M}(X)$ $\mathcal{M}(X')$ $\mathcal{M}$ $\mathcal{R}$ $\epsilon_l$ $\mathcal{M}$ $( \epsilon_c , \delta_c) -$ $\epsilon_c < \epsilon_l$ $\gamma$ $\mathcal{R}$ $\mathcal{R}_{\gamma,b}$ $\gamma =\frac{b}{e^\epsilon+b-1}$ $x$ $[ b ]$ $\mathcal{S}$ $\mathcal{A}$ $\hat{z}\leftarrow\frac{1}{b}\sum^n_{i=1}y_i$ ，并参照以下进行去偏

z \leftarrow (\hat{z}-n\gamma/2)(1-\gamma) \tag{1}

$[ 0 , 1]$ $\gamma = e^{-\epsilon_l / 2}$ 。通过数值评估可以访问更严格的边界(即,更大的放大)。

引理 1： $\sqrt{\frac{14\log(2/\delta_c)(b-1)}{n-1}}<\epsilon_c\leq1$ $\mathcal{R}_{\gamma,b}$ $\epsilon_l -$ $\mathcal{S}\circ \mathcal{R}^n$ $( \epsilon_c , \delta_c)$ $\sqrt{\frac{14\log(2/\delta_c)(e^{\epsilon_l}+b-1)}{n-1}}$

推论 1： $\mathcal{R}$ $\epsilon_l -$ $\epsilon_l\leq \log(n/\log(1/\delta_c))/2$ $\mathcal{M}$ $( \epsilon_c , \delta_c) -$ $\epsilon_c=O((1\and\epsilon_l)e^{\epsilon_l}\sqrt{\log(1/\delta_c)/n})$ 。

组成和子采样属性

组成的属性对于差分隐私的curator和local模型都是通用的。

引理 2： $\forall \epsilon.\delta\geq0,t\in\N$ $\epsilon-$ $t-fold$ $t\epsilon-$ DP

引理 3： $\forall \epsilon.\delta,\delta'\geq0,t\in\N$ $(\epsilon,\delta)-$ $t-folod$ $(\sqrt{2t\ln(1/\delta')}·\epsilon+t·\epsilon(e^\epsilon-1),k\delta+\delta')-$ DP

不进行替换 $\mathcal{K}$ 导致了子采样操作下的隐私放大。

引理 4： $\mathcal{M}:\mathbb{X}^m\rightarrow\mathbb{Y}$ $m$ $\simeq_r$ $(\epsilon,\delta)-$ $\mathcal{M'}:\mathbb{X}^n\rightarrow\mathbb{Y}$ $(\log(1+(m/n)(e^\epsilon-1)),(m/n)\delta)-$ DP。

FLAME框架

缔约方（Parties）：1 ) $n$ $d$ $x_i$ $y_i$ $\mathcal{R}$ 2 ) $\mathcal{S}$ 3 ) $\mathcal{A}$ $z$ $θ^ t←θ^t-1 + z$ $t$ 轮的全局模型。
信任边界（Trust Boundaries）： $\mathcal{O}$ $\mathcal{A}$ $\mathcal{O}$ $\mathcal{S}$ ，FLAME避免了DP - FL对任何一方的完全信任，同时能够获得比LDP - FL更好的效用。
信任分离（Trust Separation）：进一步，在我们的框架FLAME中，我们明确了哪些是隐私信息，哪些人可以接触到这些信息。我们为FLAME设计了一个细粒度的信任分离方案，并在下表中与DP - FL和LDP - FL进行了比较。
$\mathcal{S}$ $\mathcal{S}$ $\mathcal{S}$ $\mathcal{S}$ $( \epsilon_c , \delta_c) -$ $\mathcal{A}$ $\mathcal{O}$ $( \epsilon_c , \delta_c) -$ $( \epsilon_c , \delta_c) -$ $\mathcal{R}$ 来实现这个目标。
FLAME框架（FLAME Framework）： $\mathcal{E}$ $\mathcal{S}$ $\mathcal{A}$ 。
$\epsilon_l$ $pk_a$ $sk_a$ $\textbf{Randomize( · )}$ $\textbf{Shuffle ( · )}$ $\mathcal{R}_{\gamma,b}$ $\textbf{Randomize( · )}$ ，这与第( 18 )行的式( 1 )估计一致。一般的随机数发生器（e.g.拉普拉斯机制）也可以应用于这个函数，这并不影响我们后面的定理。
安全假设（Security Assumptions.）：我们假设混洗器和分析器是各自独立运行的（否则, FLAME退化为LDP - FL）。我们还假设密码原语是安全的，敌手从密文中学习任何信息都存在计算困难。
Simple Protocol (SS-Simple)： $d$ SS-Simple $\mathcal{P} = \mathcal{A}\circ\mathcal{S}\circ\mathcal{R}^n$ $\epsilon_{ld} -$ $\epsilon_{ld} = \epsilon_l / d$ SS-Simple $idx_i\leftarrow\{1,...,d\}$ $y_i\leftarrow\{\mathcal{R}_{\epsilon_{ld}}(x_{i,1}),...,\mathcal{R}_{\epsilon_{ld}}(x_{i,d})\}$ $\textbf{Randomize( · )}$ $\textbf{Shuffle ( · )}$ $π$ $m_ {π ( i )\in[ n ]}$ 。

$\mathcal{R}_{\gamma,b}$ $\mathcal{R}$ $(\epsilon_{cd},\delta_{cd})$ $\epsilon_l$ $\epsilon_c$ 的放大。

定理 1： $X\simeq_rX'$ $d$ $\mathcal{M} = \mathcal{S}\circ \mathcal{R}^n$ $( \epsilon_c , \delta_c) -$ DP，其中

\epsilon_c = d\epsilon_{cd} \and (\epsilon_{cd}\sqrt{2d\log(1/\delta_{cd})}+d\epsilon_{cd}(e^{\epsilon_{cd}}-1)) \tag{2}

\delta_c=\delta_{cd}(d+1) \tag{3}

推论 2： $\epsilon_l\leq d·\log(n/\log((d+1)/\delta_c))/2$ $\epsilon_c=O((1\and e^{\epsilon_l/d})e^{\epsilon_l/d})\log (d/\delta_c)\sqrt{d/n}$ 。

SS - Simple的局限性： $d$ $d$ $\epsilon_{ld} = \epsilon_l / d$ $y_{i,j}$ 进行随机化会注入很大的噪声。

双扩增（SS - Double）

Intuition：SS-Double $\epsilon_{ld} = \epsilon_l / d$ $k$ $k\ll d$ $\epsilon_{lk} = \epsilon_l /k$ 中获益。此外，我们注意到隐私放大可以通过子采样进一步放大，我们称之为双重放大（double amplification）。直觉上，如果加强隐私放大，在相同的中心隐私水平下，可以注入更少的噪声。
Challenge： $\mathcal{R}_{\gamma,b}$ $\mathcal{K}^β_r$ $n$ $n_s$ $β = n_s / n$ $\delta_ {cd} < 2β$ $\delta_{cd}\ll \frac{1}{dn}$ 可以忽略不计。

定理 2： $\gamma = \frac{b}{e^{\epsilon_{ld}}+b-1}$ $\delta_{cd}<2\beta$ $\mathcal{M} = \mathcal{S}\circ \mathcal{R}^{n_s}_{\gamma,b}\circ\mathcal{K}^\beta_r$ $( \epsilon_{cd} , \delta_{cd}) -$ DP，其中

\epsilon_{cd} = \log(1+\beta(e^\sqrt{\frac{14\log(\frac{2\beta}{\delta_{cd}})(e^{\epsilon_{lk}} +b-1)}{n_s-1}}-1)) \tag{4}

$\mathcal{R}_{\gamma,b}$ 类似的定理。直观上，这是因为混洗隐私放大的证明依赖于有界大小的相邻数据集，而子采样可能导致两个大小不同的相邻数据集。

Dummy Padding：虚拟填充（Dummy Padding） $n_p$ $n_n = n_p-n_s$ $\mathcal{R} ( 0 )$ $n_n$ SS-Double $\mathcal{P} = \mathcal{A}\circ\mathcal{S}_p\circ\mathcal{R}^{n_p}\circ\mathcal{K}^\beta_r$ $\mathcal{S}_p$ $\mathcal{K}^\beta_r$ SS-Double $\textbf{Randomize( · )}$ $k$ $idx_i\leftarrow \mathcal{K}^\beta_r(d)$ $j \in idx_i$ $y_i$ $y_{i,j}\leftarrow \mathcal{R}_{\epsilon_{ld}}(\tilde{x}_{i,j})$ $\textbf{Shuffle ( · )}$ 的步骤如算法3所示。

隐私与效用分析： $\mathcal{R}_{\gamma,b}$ $n_p$ $\epsilon_{cd}$ $n_p$ 意味着更多的噪声注入，如命题1所示。

定理 3： $\gamma = \frac{b}{e^{\epsilon_{lk}}+b-1}$ $\sigma_{cd}<2\beta$ $\mathcal{M}=\mathcal{S}_p \circ\mathcal{R}^{n_p}_{\gamma,b}\circ\mathcal{K}^\beta_r$ $( \epsilon_{cd} , \delta_{cd}) -$ DP，其中

\epsilon_{ck} = \sqrt{\frac{14\log(\frac{2\beta}{\delta_{cd}})(e^{\epsilon_{lk}}+b-1)}{n_p-1}} \tag{5}

\epsilon_{cd} = \log(1+\beta(e^{\epsilon_{ck}}-1)) \tag{6}

命题 1： $\mathcal{P} = \mathcal{A}\circ\mathcal{S}\circ\mathcal{R}^{n_p}\circ\mathcal{K}^\beta_r$ $O(\frac{n_p^{1/6}\log^{1/3}(1/\delta_{ck})}{n_s\epsilon^{2/3}_{ck}})$ .

$( \epsilon_{ck} , \delta_{ck}) -$ $β = k / d$ $\epsilon_l$ $\epsilon_c$ 的放大效应。

定理 4： $X\simeq_rX'$ SS-Double $d$ $\mathcal{M}=\mathcal{S}_p \circ\mathcal{R}^{\beta}\circ\mathcal{K}^\beta_r$ $( \epsilon_{c} , \delta_{c}) -$ DP，其中

\epsilon_c = 2\beta d\epsilon_{cd} \and(\epsilon_{cd}\sqrt{4\beta d \log(1/\delta_{cd})}+2\beta\epsilon_{cd}(e^{\epsilon_{cd}}-1)), \\ \delta_c = \delta_{cd}(2\beta d + 1)

推论 3： $\epsilon_l \leq \beta d \log(n_p/log((2\beta^2d+\beta)/\delta_c))/2$ ，放大的中心隐私为

\epsilon_c = O((1\and e^{\frac{\epsilon_l}{\beta d}})e^{\frac{\epsilon_l}{\beta d}}\beta^{1.5}\sqrt{\frac{d}{n_p}\log(\frac{\beta d}{\delta_c})\log(\frac{\beta^2 d}{\delta_c})}) \tag{7}

隐私放大的仿真： 为了比较SS-SimpleSS-Double $\mathcal{R}_{\gamma,b}$ 相关放大后的隐私进行了可视化。如下图所示。
$\mathcal{S}\circ \mathcal{R}^n$ （SS - Simple）：引理1和定理1
$\mathcal{S}_p\circ\mathcal{R}^{n_p}\circ\mathcal{K}^\beta_r$ （SS - Double）：定理3和4
$\epsilon_{ld}$ SS-Simple $\epsilon_{lk}$ SS-Double $\epsilon_l / \epsilon_c$ $d = 75632$ SS-Double $× 2.55$ $× 137.27$ $\mathcal{R}_{\gamma,b}$ $\epsilon_{ck}$ 的取值上有所不同。我们在实验中展示了更多的数值评估。

$Top - K$ (`Ss-Topk`)提升效用

Intuition：SS-Double $( d > n)$ $β$ $-k$ 指标是数据依赖的，从而损害了用户隐私。面临的挑战是如何在尽可能保持效用的同时，对索引隐私（index privacy）进行保护和限制。
index Privacy： $\mathcal{S}$ $\mathcal{S}$ $k$ $-k$ $k / d$ $ν$ 倍。

$j\in [d]$ $\mathbb{I}_j\in\{0,1\}$ $k(\beta=k/d)$ $j$ $\mathcal{K}^ β_ ν ( j )$ $ν$ $ν = 1$ $\mathcal{K}^ β_ ν ( j )$ 不会增加对抗成功率。

定义 3： $\mathcal{K}^ β_ ν$ $d$ $v-$ $j\in[d],v\geq1$ $\text{Pr}[\mathbb{I}_j=1|\mathcal{K}^ β_ ν(j) ]\leq v·\text{Pr}[\mathbb{I}_j=1]$ $\text{Pr}[\mathbb{I}_j=0|\mathcal{K}^ β_ ν(j) ]\geq\frac{\text{Pr}[\mathbb{I}_j=0]}{v}$ 。

$ν -$ $\text{Pr}[\mathbb{I}_j = 1] = β$ $\text{Pr}[\mathbb{I}_j = 1] = β$ $\text{Pr}[\mathbb{I}_j = 0]= 1-β$ $lk$ $k$ $- k$ $\text{Pr}[\mathbb{I}_j=1|\mathcal{K}^ β_ ν(j) ]=1/l$ $\text{Pr}[\mathbb{I}_j=1|\mathcal{K}^ β_ ν(j) ] \leq \min(v·\beta,\frac{v-1+\beta}{v})$ $l\geq \{\frac{1}{v\beta},\frac{v}{v-1+\beta}\}$ $\mathcal{K}^\beta_v$ $v-$ top索引隐私。

SS-Topk协议：SS-Topk $\mathcal{P} = \mathcal{A}\circ\mathcal{S}_p\circ\mathcal{R}^{n_p}\circ\mathcal{K}^\beta_v$ $\mathcal{R}\circ\mathcal{K}^\beta_v$ $\mathcal{S}_p$ $\mathcal{A}$ 。与SS-DoubleSS-Topk $\textbf{Randomize( · )}$ $\mathcal{K}^\beta_v$ 上有所不同，如算法4所示。

$\tilde{x}_i$ $\mathcal{K}^\beta_v$ $k$ $- k$ $S_{top}$ $k( l-1)$ $S_{non}$ $k$ $\epsilon_{lk} = \epsilon_{l} / k$ $- k$ $y_{i,j}\leftarrow \mathcal{R}_{\epsilon_{lk}}(\tilde{x}_{i,j})$ $\mathcal{R}_{\epsilon_{lk}}(0)$ $kl$ $idx_i$ $y_i$ $l$ 个消息。

隐私分析： $ν$ $l$ $l = \lceil 1 / β\rceil$ $ν = 1$ SS-Double $ν$ $\mathcal{K}^\beta_v$ SS-Topk $- k$ $- k$ 指标及其值，隐私攻击的可用性也会显著受损。

命题 2： $ν -$ $1≤ν≤1/β$ $l = \lceil1/β \rceil$ $ν = 1$ $l = 1$ 时没有实现索引隐私。

$( \epsilon_{c} , \delta_{c}) -$ $\mathcal{S}_p$ $n_p$ $ν -$ $( \epsilon_{c} , \delta_{c}) -$ SS-Topk $n_p$ 相同的情况下共享SS - Double中的双重放大效应。

$ν -$ $l$ $O ( lk )$ $n_p$ $n_p$ $n$ $β$ $ν$ 不影响均值估计的精度，因为虚拟值的个数是固定的。我们在定理5中证明了给定参数下的最强索引隐私性。

定理 5： $\mathcal{K}^\beta_v$ $n_p$ $ν = \max \{ 1，\frac{1}{\lfloor\frac{n_p}{n_β}\rfloor· β} \}$ 。

Evaluations

$d = 7850$ $n = 1000$ $( \epsilon_{} , \delta_{}) -$ $\epsilon-$ LDP )以及我们提出的SS-Simple、SS-Double、SS-Topk三种协议。

三种协议之间的比较： 对于SS-Simple、SS-DoubleSS-Topk $\mathcal{R}$ $\epsilon_l=78.5$ $\epsilon_{ld}=0.01$ ；对于SS-DoubleSS-Topk $\epsilon_{lk}=0.5$ $\mathcal{A}$ $( 0.91,5 × 10^{- 6}) -$ SS-Simple $( 0.24,5 × 10^{- 6}) -$ DP ( SS-Double / Topk )。与SS-SimpleSS-Double $4.07 \%$ 。与SS-DoubleSS-Topk $55.5 \%$ $n / n_p = 3$ $l = 16$ $ν = 3.125$ 。
DP - FL / LDP比较：SS-Simple $( 0.24,5 × 10^{ - 6})-$ SS-Topk $33.94 \%$ 的准确率。这是我们工作的一个key observation，因为针对一维任务的传统工作声称混洗模型只站在LDP和DP之间。
SS-Double $( 0.24,5 × 10^{ - 6})-$ SS-Topk $- k$ 提高了效用。2 )双放大效应：如果只统计SS-TopkSS-Topk $\epsilon_c = 20.53,\delta_c = 5 × 10^{ - 6}$ $( 20.53,5 × 10^{ - 6})-$ DP的另一个baseline。我们观察到这一行接近非私有版本，并且比SS-TopkSS-Topk $- k$ 提升都是比DP - FL更好的性能所必需的。
不同参数下的比较： $n_p,β$ $\epsilon_l$ ，结果见下图6，7和8。
1 )从图6中可以明显看出，每个维度更大的本地隐私预算导致更高的测试精度。
$n / n_p$ $n_p$ 是调节隐私和效用权衡的关键。
$β$ $β = 1 / 10$ $( 4.696,10^{- 5}) -$ $1.48 \%$ 。
Privacy Amplification： 我们在图9和图10中用拉普拉斯机制的Bennett不等式来说明前面评估中的整体放大。
这验证了只要放大的界可以通过闭式解或数值计算得到，那么们的定理1，4和推论2，3对于任何本地随机数发生器就都是通用的。